// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-04 20:59
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

public class FindUnsortedSubarray {
    /**
     * 寻找最小连续升序数组
     */
    public int findUnsortedSubarray(int[] nums) {
        int n = nums.length;
        // 使用单调栈 -> 记录逆序对出现的位置
        // 特殊: 只出现start 但是并不出先end -> 需要记录最小满足条件
        int start = 0, end = 0;
        int[] stack = new int[n];
        int top = 0;
        // 用于判断第一次出现的标志
        int flag = 0;
        stack[0] = nums[0];
        for (int i = 1; i < n; i++) {
            if (stack[top] > nums[i]) {
                // 出现了逆序对
                if (flag == 0) {
                    // 当前的逆序对是第一次出现,而且是因为前面的一个值比较大
                    // 确定逆序对开始索引
                    int t = nums[i];
                    int k = i;
                    while (k > 0 && t < nums[k - 1]) {
                        k--;
                    }
                    // 可以将线性查找替换为二分查找
                    start = k;
                } else {
                    // 当前出现的逆序对并不是第一次出现
                    end = i;
                }
                flag++;
            } else {
                // 新来的数值并不是逆序
                if (flag == 1) {
                    // 第一次出现逆序的时候保留前一个值
                    stack[top] = nums[i - 1];
                }
                stack[++top] = nums[i];

            }
            if (nums[i] < nums[start]) {
                // 记录没有出现逆序对时候的位置
                end = i;
            }
        }

        while (start != 0 && nums[start - 1] > nums[end]) {
            start--;
            if (start == 0) {
                break;
            }
        }


        // 需要判断一次逆序对都没出现的时候
        return flag == 0 ? 0 : Math.max(end - start + 1, 0);
    }

    @Test
    public void shout() {
        // int[] nums = {2, 6, 4, 8, 10, 9, 15};
        //int[] nums = {1, 2, 3, 4};
        // int[] nums = {2, 1};
        int[] nums = {2, 5, 3, 1, 4};
        //int[] nums = {2, 3, 3, 2, 4};
        //int[] nums = {2, 3, 3, 2, 4, 5, 6, 7, 8, 1};
        System.out.println(findUnsortedSubarray(nums));
    }
}
